package dfs;

/**
 * @author pengfei.hpf
 * @date 2020/2/15
 * @verdion 1.0.0
 *
 * Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
 *
 * Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
 *
 * Example 1:
 *
 * [[0,0,1,0,0,0,0,1,0,0,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,1,1,0,1,0,0,0,0,0,0,0,0],
 *  [0,1,0,0,1,1,0,0,1,0,1,0,0],
 *  [0,1,0,0,1,1,0,0,1,1,1,0,0],
 *  [0,0,0,0,0,0,0,0,0,0,1,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
 * Example 2:
 *
 * [[0,0,0,0,0,0,0,0]]
 * Given the above grid, return 0.
 * Note: The length of each dimension in the given grid does not exceed 50.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-area-of-island
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxAreaOfIsland {

    private int[][] dir = new int[][]{{-1,0}, {0,-1}, {1,0},{0,1}};

    public int maxAreaOfIsland(int[][] grid){
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int max = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j =0; j < grid[0].length; j ++){
                if(grid[i][j] == 1){
                    int count = dfs(grid, i, j);
                    if(count > max){
                        max = count;
                    }
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int i, int j){
        if(i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] == 0){
            return 0;
        }
        int count = 1;
        grid[i][j] = 0;
        for(int m = 0; m < dir.length; m ++){
            count += dfs(grid, i + dir[m][0], j + dir[m][1]);
        }
        return count;
    }
}
